//
//  Problem1071.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/21.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1071. 字符串的最大公因子
 对于字符串 S 和 T，只有在 S = T + ... + T（T 自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

 返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

 示例 1：
     输入：str1 = "ABCABC", str2 = "ABC"
     输出："ABC"
 示例 2：
     输入：str1 = "ABABAB", str2 = "ABAB"
     输出："AB"
 示例 3：
     输入：str1 = "LEET", str2 = "CODE"
     输出：""
 提示：
     1 <= str1.length <= 1000
     1 <= str2.length <= 1000
     str1[i] 和 str2[i] 为大写英文字母
 */
@objcMembers class Problem1071: NSObject {
    func solution() {
        print(gcdOfStringsYouGCDPan("ABCABC", "ABC"))
        print(gcdOfStringsYouGCDPan("ABABAB", "ABAB"))
        print(gcdOfStringsYouGCDPan("LEET", "CODE"))
        
    }
    func gcdOfStrings(_ str1: String, _ str2: String) -> String {
        if str1.count == 0 || str2.count == 0 {
            return ""
        }
        
        let (start, end) = getGCD(0, str1.count-1, 0, str2.count-1)
        
        
        let str = String(str1[str1.index(str1.startIndex, offsetBy: start)...str1.index(str1.startIndex, offsetBy: end)])
        
        if str1.replacingOccurrences(of: str, with: "").count == 0 && str2.replacingOccurrences(of: str, with: "").count == 0 {
            return str
        }
        
        return ""
    }
    
    /*
     012 345 678  自己理解的gcd算法
     abc abc abc
     abc abc
     */
    func getGCD(_ start1: Int, _ end1: Int, _ start2: Int, _ end2: Int) -> (Int, Int) {
        if  end1 - start1 == end2 - start2 {
            return (start1, end1)
        } else if end1 - start1 > end2 - start2 {
            return getGCD(end1-(end1 - start1 - end2 + start2)+1, end1, start2, end2)
        } else {
            return getGCD(start1, end1, end2-(end2 - start2 - end1 + start1)+1, end2)
        }
    }
    
    /*
     优化GCD算法
     */
    func gcdOfStringsYouGCD(_ str1: String, _ str2: String) -> String {
        if str1.count == 0 || str2.count == 0 {
            return ""
        }
        
        let end = gcd(str1.count, str2.count)
        
        
        let str = String(str1[str1.startIndex..<str1.index(str1.startIndex, offsetBy: end)])
        print("end = ", end, str)
        if str1.replacingOccurrences(of: str, with: "").count == 0 && str2.replacingOccurrences(of: str, with: "").count == 0 {
            return str
        }
        
        return ""
    }
    
    // GCD算法
    func gcd(_ end1: Int, _ end2: Int) -> Int {
        return 0 == end2 ? end1 : gcd(end2, end1 % end2)
    }
    
    // 优化判断：之前的判断是找打最小的公约数，然后每个字符串替换公约数 是否是空
    // 优化：abcabc abc  如果符合的话：  str1 + str2 == str2 + str1
    
    func gcdOfStringsYouGCDPan(_ str1: String, _ str2: String) -> String {
        if str1 + str2 != str2 + str1 {
            return ""
        }
        
        let end = gcd(str1.count, str2.count)
        
        
        return String(str1[str1.startIndex..<str1.index(str1.startIndex, offsetBy: end)])
    }
}
